// 奇偶游戏.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*


https://www.acwing.com/problem/content/241/
小 A 和小 B 在玩一个游戏。

首先，小 A 写了一个由 0 和 1 组成的序列 S，长度为 N。

然后，小 B 向小 A 提出了 M 个问题。

在每个问题中，小 B 指定两个数 l 和 r，小 A 回答 S[l∼r] 中有奇数个 1 还是偶数个 1。

机智的小 B 发现小 A 有可能在撒谎。

例如，小 A 曾经回答过 S[1∼3] 中有奇数个 1，S[4∼6] 中有偶数个 1，现在又回答 S[1∼6] 中有偶数个 1，显然这是自相矛盾的。

请你帮助小 B 检查这 M 个答案，并指出在至少多少个回答之后可以确定小 A 一定在撒谎。

即求出一个最小的 k，使得 01 序列 S 满足第 1∼k 个回答，但不满足第 1∼k+1 个回答。

输入格式
第一行包含一个整数 N，表示 01 序列长度。

第二行包含一个整数 M，表示问题数量。

接下来 M 行，每行包含一组问答：两个整数 l 和 r，以及回答 even 或 odd，用以描述 S[l∼r] 中有偶数个 1 还是奇数个 1。

输出格式
输出一个整数 k，表示 01 序列满足第 1∼k 个回答，但不满足第 1∼k+1 个回答，如果 01 序列满足所有回答，则输出问题总数量。

数据范围
N≤109,M≤5000
输入样例：
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
输出样例：
3
*/



/*
//带权边
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 20010;

int n, m;
int p[N], d[N];
unordered_map<int, int> S;

int get(int x)
{
	if (S.count(x) == 0) S[x] = ++ n;
	return S[x];
}

int find(int x)
{
	if (p[x] != x)
	{
		int root = find(p[x]);
		d[x] += d[p[x]];
		p[x] = root;
	}
	return p[x];
}

int main()
{
	cin >> n >> m;
	n = 0;

	for (int i = 0; i < N; i ++ ) p[i] = i;

	int res = m;
	for (int i = 1; i <= m; i ++ )
	{
		int a, b;
		string type;
		cin >> a >> b >> type;
		a = get(a - 1), b = get(b);

		int t = 0;
		if (type == "odd") t = 1;

		int pa = find(a), pb = find(b);
		if (pa == pb)
		{
			if (((d[a] + d[b]) % 2 + 2) % 2 != t)
			{
				res = i - 1;
				break;
			}
		}
		else
		{
			p[pa] = pb;
			d[pa] = d[a] ^ d[b] ^ t;
		}
	}

	cout << res << endl;

	return 0;
}
*/

/*
//扩展域
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 40010, Base = N / 2;

int n, m;
int p[N];
unordered_map<int, int> S;

int get(int x)
{
	if (S.count(x) == 0) S[x] = ++n;
	return S[x];
}

int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int main()
{
	cin >> n >> m;
	n = 0;

	for (int i = 0; i < N; i++) p[i] = i;

	int res = m;
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		string type;
		cin >> a >> b >> type;
		a = get(a - 1), b = get(b);

		if (type == "even")
		{
			if (find(a + Base) == find(b))
			{
				res = i - 1;
				break;
			}
			p[find(a)] = find(b);
			p[find(a + Base)] = find(b + Base);
		}
		else
		{
			if (find(a) == find(b))
			{
				res = i - 1;
				break;
			}

			p[find(a + Base)] = find(b);
			p[find(a)] = find(b + Base);
		}
	}

	cout << res << endl;

	return 0;
}
*/

#include <iostream>
#include <unordered_map>
#include <memory.h>
#include <string>

using namespace std;

const int N = 40010;
const int BASE = N / 2;
int n, m;
int p[BASE*2];
unordered_map<int ,int > S;


int get(int x) {
	if (S.count(x) == 0) {
		S[x] = ++n;
	}

	return S[x];
}
 
int find(int x) {
	if (p[x] != x) {
		p[x] = find(p[x]);
	}

	return p[x];
}

 
int main()
{
	cin >> n >> m;
	n = 0;
	for (int i = 0; i < N; i++) p[i] = i;
	int res = m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		string type;
		cin >> a >> b >> type;
		a = get(a - 1); b = get(b);

		if (type == "even") {
			if (find(a + BASE) == find(b)) {
				res = i - 1; break;
			}
			else {
				p[find(a)] = find(b);
				p[find(a + BASE)] = find(b + BASE);
			}
		}
		else {
			if (find(a) == find(b)) {
				res = i - 1; break;
			}
			else {
				p[find(a + BASE)] = find(b);
				p[find(a)] = find(b + BASE);
			}
		}
	} 
    
	cout << res << endl;

	return 0;
}
